package stack;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class leetcode316去除重复字母 {
    public String removeDuplicateLetters(String s) {
        int length = s.length();
        Stack<Character> stack = new Stack<>();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            map.put(ch, map.get(ch) - 1);
            if (stack.contains(ch)) {
                continue;
            }
            while (!stack.isEmpty() && stack.peek() > ch) {
                if (map.get(stack.peek()) > 0) {
                    stack.pop();
                } else {
                    break;
                }
            }
            stack.push(ch);
        }
        StringBuilder str = new StringBuilder();
        while (!stack.isEmpty()) {
            str.insert(0, stack.pop());
        }
        return str.toString();
    }
}
